package FifthWeek;

public class Monday {
    //287、寻找重复数
    public int findDuplicate(int[] nums) {
        int n = nums.length;
        int[] retNums = new int[n - 1];//初始化全为0
        for(int num : nums) {
            if (retNums[num - 1] != 0) {
                return num;
            }
            //第一次判断后对应的位置放入数据，当再次判断这个数的时候就不会为0，就会返回数据
            retNums[num - 1] = num;
        }
        return -1;
    }

    public int findDuplicate2(int[] nums) {
        //快慢指针
        //案例：[1,3,4,2,2]
        //第一按照快慢指针找环，我们快慢指针走的是数组这个数值对应的下标
        //1 3 4 2 2  -> 对应下标：0 1 2 3 4
        //slow：0，fast：0，这个位置对应的值是1，所以走到1 下标对应的位置，
        //slow：1，fast：1，因为fast走两步，所以fast这个位置的值是3，所以走到下标为3的位置
        //slow：1，fast：3，这就走完一步，之后按这个规则走，直到fast和slow相遇之后，把slow置为0，再slow和fast一步一步走
        //这样走会出现循环是因为，4这个值对应下标为2，最后一个2这个值对应的下标是4，所以会出现循环
        //比如上面呢，最后相遇在最后一个2上，之后还是按照上面的步骤走，这回是一步一步，直到在次相遇对应的就是重复数字
        int slow = 0,fast = 0;
        //先走后判断，使用do-while
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }while (slow != fast);
        //这时候相遇
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }

    public int findDuplicate1(int[] nums) {
        //二分查找
        //因为数组长度为n+1是从 1-n递增的数组，如果出现重复数字那么其对应的重复数字在数组中小于等于这个数字的个数会比这个数字大
        //并且之后的数字也会比其对应的数大
        //比如：1 3 4 2 2  -> 长度为5 = 4 + 1，对应的n就是数组中最大的数字
        //对应的数字为                    1 2 3 4
        //对于数字的小于等于这个数的个数为    1 3 4 5
        //所以这里的二分查找不去比较数组对应下标的值，而是根究 1-n递增的这个特性，和出现重复数后对应的小于等于这个数的个数也会增加
        int n = nums.length - 1;
        int left = 1,right = n;
        while(left < right) {
            int mid = left + (right - left) / 2;
            int minMid = 0;
            for (int i = 0;i <= n;i++) {
                if (nums[i] <= mid) {
                    minMid++;
                }
            }
            if (minMid <= mid) {
                //说明这个 mid 这个位置的值及之前的值都没有重复数字
                left = mid + 1;
            }else {
                //minMid > mid，说明这个位置或者这个位置之前出现过重复数，所以不能放过这个位置的数
                right = mid;
            }
        }
        return left;
    }
}
